/**
 * 
 */
package array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;

import utils.PrintUtils;

/**
 * given input as an array of strings. Such as: {"apple Orange", "ORANGE apple",
 * "APPLe oRange", "HI There", "THERE hI"}; return an array of strings. in the
 * above case, will return "APPLe oRange", "THERE hI".
 * 
 * Here are the rules: 1. two strings are the same when words matches(case
 * insensitive) and order doesn't matter, so "apple Orange" == "APPLe oRange" ==
 * "ORANGE apple". 2. if multiple identical strings exist, only return the one
 * that occurs at the last location, so "APPLe oRange" and "THERE hI" will in
 * the result. 3. the relative order cannot be changed, so we cannot have result
 * as "THERE hI", "APPLe oRange".
 * 
 * @author xyyi
 * @since 2013.01.12
 * @version 2013.01.12
 * @see http://blog.sina.com.cn/s/blog_b9285de20101h24d.html
 */
public class RemoveDuplicatedString {

	/**
	 * 
	 */
	public RemoveDuplicatedString() {
		// TODO Auto-generated constructor stub
	}

	public String[] removeDuplicationHT(String[] strings) {
		if (strings == null || strings.length <= 1) {
			return strings;
		}

		HashMap<String, Integer> hash = new HashMap<String, Integer>();
		for (int i = 0; i < strings.length; i++) {
			hash.put(convertKey(strings[i]), i);
		}

		Integer[] indexes = hash.values().toArray(
				new Integer[hash.values().size()]);
		Arrays.sort(indexes);

		String[] result = new String[indexes.length];
		for (int i = 0; i < result.length; i++) {
			result[i] = strings[indexes[i]];
		}

		return result;
	}

	public String[] removeDuplicationHTHS(String[] strings) {
		if (strings == null || strings.length <= 1) {
			return strings;
		}

		final HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
		final HashSet<Integer> hashSet = new HashSet<Integer>();

		for (int i = 0; i < strings.length; i++) {
			String key = convertKey(strings[i]);
			if (hashMap.containsKey(key)) {
				hashSet.add(hashMap.get(key));
			}
			hashMap.put(key, i);
		}

		String[] result = new String[strings.length - hashSet.size()];
		for (int i = 0, j = 0; i < strings.length; i++) {
			if (!hashSet.contains(i)) {
				result[j++] = strings[i];
			}
		}

		return result;
	}

	public String[] removeDuplicationLHT(String[] strings) {
		if (strings == null || strings.length <= 1) {
			return strings;
		}

		LinkedHashMap<String, String> hash = new LinkedHashMap<String, String>();
		for (String s : strings) {
			hash.put(convertKey(s), s);
		}

		return hash.values().toArray(new String[hash.size()]);
	}

	public String[] removeDuplicationHSLST(String[] strings) {
		if (strings == null || strings.length <= 1) {
			return strings;
		}
		HashSet<String> hash = new HashSet<String>();
		List<String> list = new ArrayList<String>();
		for (int i = strings.length - 1; i >= 0; i--) {
			String key = convertKey(strings[i]);
			if (!hash.contains(key)) {
				list.add(strings[i]);
			}
			hash.add(key);
		}

		Collections.reverse(list);
		return list.toArray(new String[list.size()]);
	}

	private String convertKey(String string) {
		assert (string != null && !string.trim().isEmpty());

		final String[] arr = string.toLowerCase().split(" ");

		Arrays.sort(arr, java.text.Collator.getInstance());

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < arr.length - 1; i++) {
			sb.append(arr[i]).append(' ');
		}
		sb.append(arr[arr.length - 1]);

		return sb.toString();
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] words = { "apple Orange", "ORANGE apple", "APPLe oRange",
				"HI There", "THERE hI" };
		PrintUtils.printArray(words);

		RemoveDuplicatedString rds = new RemoveDuplicatedString();
		String[] result = rds.removeDuplicationHSLST(words);
		PrintUtils.printArray(result);
	}

}
